AGC013 C Ants on a Circle

700点

code: agc013_c.js

solve() {

const nlt = input.nextIntArr();

const N = nlt0; const L = nlt1; const T = nlt2;

const xwList = input.nextIntRange(N)

.map(e => {return { x: e0, w: e1 == 1 ? 1 : -1 }});

const lastPos = xwList.map(xw => (xw.x + xw.w * (T%L) + L) % L);

// 蟻同士がすり抜けるとした時に、

// 蟻1の動きをする蟻がT秒間に他の蟻にぶつかる蟻の総数

let sum = 0;

const xw0 = xwList0;

for (let i = 1; i < N; ++i) {

const xw = xwListi;

// 同じ向きの場合すれ違わない

if (xw.w == xw0.w) continue;

// initial distance

const d = (xw0.w * (xw.x - xw0.x) + L) % L;

// 移動速度の和は 2より

// 2 * T <= (x - 1)L + d を満たす最大のx

// <=> (2 * T - d) / L <= x

const x = ((2 * T + L - d) / L | 0);

sum += x; sum %= N;

}

const idx = (xw0.w * sum + N) % N;

const pos = lastPos0;

_.sort(lastPos);

let rotate = (xw0.w == 1

? _.binarySearch(lastPos, pos + 1) - 1

: _.binarySearch(lastPos, pos))

- idx

;

return _.rotate(lastPos, rotate).join('\n');

}

時計回り, 反時計回りを1,-1で管理すると楽

1人分の衝突を考える(解説参照)

コーナーケースではまりがち

蟻の位置が同じ場合 (衝突後の座標で考える)

蟻同士の衝突回数 (ちゃんと式変形するのがよい)